package style.Leetcode.初级算法.array.array_20221017_2_最长重复子数组;

/**
 * 718. 最长重复子数组
 * <p>
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 * 示例 2：
 * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
 * 输出：5
 */
public class Solution {
    /**
     * 思路：滑动窗口
     * 小数组固定不变，大数组移动
     * （1）大数组在小数组的左侧，重合长度慢慢变长
     * （2）大数组在小数组的中间，重合长度不变
     * （3）大数组在小数组的右侧，重合长度慢慢变短
     */
    public int findLength1(int[] nums1, int[] nums2) {
        return nums1.length <= nums2.length ? findMax(nums1, nums2) : findMax(nums2, nums1);
    }

    public int findMax(int[] nums1, int[] nums2) {
        int max = 0;
        int m = nums1.length, n = nums2.length;
        /**
         nums1,nums2 中较短的数组不动，这里默认nums1，较长的数组滑动
         初始位置：nums2右边界挨着nums1左边界，nums2从左往右滑动
         */
        // 第一阶段：nums2从左往右滑动，两数组重合部分长度不断增加，重合部分长度len从1开始增加
        // 重合部分：nums1起点下标0，nums2起点下标n-len，

        for (int len = 0; len <= m; len++) {
            max = Math.max(max, maxLen(nums1, 0, nums2, n - len, len));
        }

        // 第二阶段：nums2从左往右滑动，两数组重合部分长度不变，重合部分长度始终为nums1长度m
        //  重合部分：nums1起点下标0，nums2起点下标n-m，然后递减
        for (int j = n - m; j >= 0; j--) {
            max = Math.max(max, maxLen(nums1, 0, nums2, j, m));
        }

        // 第三阶段：nums2从左往右滑动，两数组重合部分长度递减，重合部分长度始终为nums1长度m-i
        //  重合部分：nums1起点下标i，递增，nums2起点下标0
        for (int i = 1; i < m; i++) {
            max = Math.max(max, maxLen(nums1, i, nums2, 0, m - i));
        }
        return max;
    }

    /**
     * nums1中下标i开始，
     * nums2中下标j开始，
     * 长度为len子数组中，
     * 最长公共子数组(注意要连续)长度
     */
    public int maxLen(int[] nums1, int i, int[] nums2, int j, int len) {
        int count = 0, res = 0;
        for (int k = 0; k < len; k++) {
            if (nums1[i + k] == nums2[j + k]) {
                count++;
            } else if (count > 0) {
                //进入到这个if判断体里面，说明当前 nums1[i+k]!=nums2[j+k],即之前的公共子数组不再连续，
                // 所以要记录最大值，同时将count置零
                res = Math.max(count, res);
                count = 0;
            }
        }
        /**
         1，count>0,说明有公共子数组是以nums1[i+len-1],nums2[j+len-1]结尾的，
         上面最后一步for循环没有进入到else if判断题里面，所以最终结果要取当前count和res的最大值
         2，count=0，说明res已经更新过了，res即为最终结果
         */
        return count > 0 ? Math.max(count, res) : res;
    }

    /**
     * 思路：动态规划
     *
     */
    public int findLength2(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int[][] dp = new int[l1 + 1][l2 + 1];  // dp[i][j]表示A的前i项与B的前j项的最长后缀长度
        int res = 0;
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                dp[i][j] = 0;
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findLength2(new int[]{1, 23, 2}, new int[]{23, 2}));
    }
}
